package com.soul.sort;

/**
 * 希尔排序
 */
public class ShellSort {

    //插入排序的变增量版本
    public static void sort(int[] a){
        int d = a.length / 2;
        //增量为1则为插入排序
        while(true){
            for (int i = d; i < a.length; i++) {
                int t = a[i];
                for (int j = i; j >= d && a[j-d]>t; j-=d) {
                    SortUtil.swap(a,j,j-d);
                }
            }
            if (d == 1)break;
            //改变增量的值
            d = (d - 1) / 2 <= 0 ? 1 : (d - 1) / 2;
        }
    }
}
